//给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。 
//
// 
//
// 
// 
// 示例 1： 
//
// 
//输入：s = "(()"
//输出：2
//解释：最长有效括号子串是 "()"
// 
//
// 示例 2： 
//
// 
//输入：s = ")()())"
//输出：4
//解释：最长有效括号子串是 "()()"
// 
//
// 示例 3： 
//
// 
//输入：s = ""
//输出：0
// 
//
// 
//
// 提示： 
//
// 
// 0 <= s.length <= 3 * 104 
// s[i] 为 '(' 或 ')' 
// 
// 
// 
// Related Topics 栈 字符串 动态规划 
// 👍 1638 👎 0


package leetcode.editor.cn.lc32;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;

public class LongestValidParentheses{
    public static void main(String[] args){
        Solution solution = new Solution();
        int i = solution.longestValidParentheses(")())");

        // *** 这个官方题解有意思
        System.out.println(i);
    }
}
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int longestValidParentheses(String s) {
        char[] chars = s.toCharArray();
        return longestValidParentheses(chars, 0, chars.length - 1);
    }

    private int longestValidParentheses(char[] chars, int head, int tail) {
        List<int[]> ranges = new ArrayList<>();
        int longest = 0;

        LinkedList<Integer> lefts = new LinkedList<>();

        int left =0;
        for (int i = head; i <= tail; i++) {
            if (chars[i] == '(') {
                lefts.push(i);
                left++;
            }else {
                if (!lefts.isEmpty()) {
                    Integer pop = lefts.pop();
                    ranges.add(new int[]{pop,i});
                }
            }
        }
        System.out.println(ranges);


        ranges.sort(Comparator.comparingInt(o -> o[0]));

        LinkedList<int[]> merged = new LinkedList<>();

        for (int i = 0; i < ranges.size(); i++) {
            int[] prec = ranges.get(i);
            for (int j = i+1; j < ranges.size(); j++) {
                int[] suc = ranges.get(j);
                if (prec[0] < suc[0] && prec[1] > suc[1]) {
                    i = j;
                } else if (prec[1] + 1 == suc[0]) {
                    prec[1] = suc[1];
                    i = j;
                }else {
                    break;
                }
            }
            merged.push(prec);
        }

        // 合并区间
        for (int[] range : merged) {
            longest = Math.max(longest, range[1] - range[0] + 1);
        }



        return longest;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

